Obeleži sve kategorije koje odgovaraju problemu

Скупови и мапе (речници)

Скупови

У програмима често имамо потребе да одржавамо скуп елемената (без дупликата), у који ефикасно можемо да додајемо елементе, из кога ефикасно можемо да избацујемо елементе и за који ефикасно можемо да проверавамо да ли је нека задата вредност елемент скупа. Савремени програмски језици у својим библиотекама пружају структуре података које нуде баш ове операције.

У језику C++ скуп је подржан кроз две класе: set<Т> и unordered_set<Т>, где је Т тип елемената скупа (за њихово коришћење је потребно укључити заглавље <set> тј. <unordered_set>). Имплементација је различита (прва је заснована на балансираним бинарним дрветима, а друга на хеш-табелама), па су им временске и просторне карактеристике донекле различите.

Скупови подржавају следеће основне операције (за преглед свих операција упућујемо читаоца на документацију):

• insert - умеће нови елемент у скуп (ако је елемент већ у скупу, операција нема ефекта). Када се користи set, сложеност уметања је \(O(\log{k})\), где је \(k\) број елемената у скупу, а када се користи unordered_set, сложеност најгорег случаја је \(O(k)\), док је просечна сложеност \(O(1)\), при чему је амортизована цена сваког додавања у склопу већег броја узастопних додавања такође \(O(1)\). Нагласимо и да константе код сложености \(O(1)\) могу бити релативно велике и да уметање не можемо сматрати јако брзом операцијом. Честа операција је додавање \(n\) елемената у скуп. Најгора сложеност је ако су сви елементи различити и у случају уређеног скупа износи приближно \(\log{1} + \log{2} + \ldots + \log{n}\), за шта се може показати да је \(O(n \log{n})\).

• erase - уклања дати елемент из скупа (ако елемент не постоји у скупу, скуп се не мења). Сложеност је иста као у случају уметања.

• find - проверава да ли скуп садржи дати елемент и враћа итератор на њега или end ако је одговор негативан. Тако се провера припадности елемента e скупу s може извршити са if (s.find(e) != s.end()) ... Сложеност најгорег случаја ове операције ако се користи set је \(O(\log{k})\), а ако се користи unordered_set сложеност најгорег случаја је \(O(k)\), али је просечна сложеност \(O(1)\).

• size - враћа број елемената скупа.

Могућа је и итерација кроз елементе скупа коришћењем петље облика for (T element : skup), при чему се елементи колекције set набрајају у сортираном, а unordered_set у прилично насумичном редоследу (редослед је одређен хеш-функцијом која се користи и на њега се, као што само име unordered говори, не треба ослањати).

Ако се у скуп стављају елементарни типови података (бројеви, ниске, …), тада се користи подразумевани поредак у случају уређених тј. подразумевана хеш-функција у случају неуређених скупова (на пример, у случају бројева подразумевани поредак је растући). Ово је могуће променити, али излази ван домена овог материјала. Да би се формирао скуп елемената неког типа над којим није дефинисан подразумевани поредак нити хеш-функција (најчешће скуп структура или објеката неке класе), потребно је посебно дефинисати функцију поретка у случају коришћења уређених тј. хеш-функцију у случају коришћења неуређених скупова. Издвојићемо само случај када желимо да направимо скуп у ком су елементи уређени нерастуће (при чему на типу података постоји подразумевани неопадајући поредак). Такав скуп је најједноставније дефинисати коришћењем set<T, greater<T>>, где је за употребу greater потребно укључити заглавље <functional>.

Уређени скупови (колекција set) подржавају и методе:

• lower_bound(x) - проналази најмањи елемент скупа који је већи или једнак од дате вредности x и враћа итератор који указује на њега (или end, ако такав елемент не постоји),

• upper_bound(x) - проналази најмањи елемент скупа који је строго већи од дате вредности x и враћа итератор који указује на њега (или end, ако такав елемент не постоји).

Подразумевани поредак елемената у скупу је растући и методе lower_bound и upper_bound раде у односу на тај поредак (при чему се поредак може променити приликом дефинисања скупа и примене ових функција, навођењем другачије функције поређења).

Мултискупови

Скупови, као и у математици, не могу да садрже дупликате. Када се елемент који већ постоји у скупу убацује у скуп методом insert, скуп се не мења. Једно уопштење скупова дају мултискупови у којима је допуштено понављање елемената. Мултискупови су подржани библиотечком структуром multiset<T>, која се користи на потпуно исти начин као и set<T> (за њено коришћење је такође довољно укључити заглавље <set>).

Мапе (речници)

Програмски језик C++ пружа подршку за креирање мапа (речника, асоцијативних низова) који представљају колекције података у којима се кључевима неког типа придружују вредности неког типа (не обавезно истог). На пример, именима месеци (подацима типа string) можемо доделити број дана (податке типа int). Речници се представљају објектима типа map<TipKljuca, TipVrednosti>, дефинисаном у заглављу <map>. На пример,

map<string, int> brojDana =
{
    {"januar", 31},
    {"februar", 28},
    {"mart", 31},
    ...
};

Приметимо да смо иницијализацију мапе извршили тако што смо навели листу парова облика {kljuc, vrednost}. Иницијализацију није неопходно извршити одмах током креирања, већ је вредности могуће додавати (а и читати) коришћењем индексног приступа (помоћу заграда []).

map<string, int> brojDana;
brojDana["januar"] = 31;
brojDana["februar"] = 28;
brojDana["mart"] = 31;
...

Мапу, дакле, можемо схватити и као низ тј. вектор у коме индекси нису обавезно из неког целобројног интервала облика \([0,n)\), већ могу бити произвољног типа.

Претрагу кључа можемо остварити методом find која враћа итератор на пронађени елемент тј. итератор иза краја мапе (који добијамо методом или функцијом end), ако елемент не постоји. На пример,

string mesec;
cin >> mesec;
auto it = brojDana.find(mesec);
if (it != end(brojDana))
   cout << "Broj dana: " + *it << endl;
else
   cout << "Mesec nije korektno unet" << endl;

Све елементе речника могуће је исписати коришћењем петље for. На пример,

for (auto& p : brojDana)
     cout << p.first << ": " << p.second << endl;

Алтернативно, можемо експлицитно користити итераторе

for (auto it = brojDana.begin(); it != brojDana.end(); it++)
     cout << it->first << ": " << it->second << endl;

Приметимо да смо у првом случају користили референцу да се пар елемената не би копирао у сваком кораку петље. У другом случају се користе итератори и оригиналном пару елемената се приступа дереференцирањем итератора.

У случају уређених мапа, итерација се врши у сортираном редоследу кључева.

Постоји и облик неуређене мапе (unordered_map из истоименог заглавља), која може бити у неким ситуацијама мало бржа него уређена (сортирана) мапа, но то је обично занемариво. Кључеви сортиране мапе могу бити само они типови који се могу поредити релацијским операторима, док кључеви неуређене мапе могу бити само они типови који се могу лако претворити у број (тзв. хеш-вредност). Ниске, које ћемо најчешће користити као кључеве, задовољавају оба услова.

Скупови и мапе (речници)

Скупови

У програмима често имамо потребе да одржавамо скуп елемената (без дупликата), у који ефикасно можемо да додајемо елементе, из кога ефикасно можемо да избацујемо елементе и за који ефикасно можемо да проверавамо да ли је нека задата вредност елемент скупа. Савремени програмски језици у својим библиотекама пружају структуре података које нуде баш ове операције.

У језику C# скуп је подржан кроз две класе: SortedSet<Т> и HashSet<Т>, где је Т тип елемената скупа. Имплементација је различита (прва је заснована на балансираним бинарним дрветима, а друга на хеш-табелама), па су им временске и просторне карактеристике донекле различите.

Скупови подржавају следеће основне операције (за преглед свих операција упућујемо читаоца на документацију):

• Add - умеће нови елемент у скуп (ако је елемент већ у скупу, операција нема ефекта). Када се користи SortedSet сложеност уметања је O(\log{k}), где је k број елемената у скупу, а када се користи HashSet, сложеност најгорег случаја је \(O(k)\), док је просечна сложеност \(O(1)\), при чему је амортизована сложеност узастопног додавања већег броја елемената такође \(O(1)\). Нагласимо и да константе код сложености \(O(1)\) могу бити релативно велике и да уметање не можемо сматрати јако брзом операцијом. Честа операција је додавање \(n\) елемената у скуп. Најгора сложеност је ако су сви елементи различити и у случају уређеног скупа износи приближно \(\log{1} + \log{2} + \ldots + \log{n}\), за шта се може показати да је \(O(n \log{n})\).

• Remove - уклања дати елемент из скупа. Сложеност је иста као у случају уметања.

• Contains - проверава да ли скуп садржи дати елемент. Сложеност најгорег случаја ове операције ако се користи SortedSet је O(\log{k}), а ако се користи HashSet сложеност најгорег случаја је O(k), али је просечна сложеност O(1).

Мапе (речници)

Програмски језик C# пружа подршку за креирање речника (мапа, асоцијативних низова) који представљају колекције података у којима се кључевима неког типа придружују вредности неког типа (не обавезно истог). На пример, именима месеци (подацима типа string) можемо доделити број дана (податке типа int). Речници се представљају објектима типа Dictionary<TipKljuca, TipVrednosti> из библиотеке System.Collections.Generic. На пример,

var brojDana = new Dictionary<string, int>()
{
    {"januar", 31},
    {"februar", 28},
    {"mart", 31},
    ...
};

Приметимо да смо речник морали да креирамо помоћу кључне речи new и да смо након тога навели листу парова облика {kljuc, vrednost}. Речник није неопходно иницијализовати одмах током креирања, већ је вредности могуће додавати (а и читати) коришћењем индексног приступа (помоћу заграда []).

var brojDana = new Dictionary<string, int>();
brojDana["januar"] = 31;
brojDana["februar"] = 28;
brojDana["mart"] = 31;
...

Речник, дакле, можемо схватити и као низ тј. листу у коме индекси нису обавезно из неког целобројног интервала облика \([0,n)\), већ могу бити произвољног типа.

Проверу да ли је неком кључу придружена вредност у речнику можемо остварити методом ContainsKey (она враћа true ако и само је датом кључу придружена нека вредност). Уместо да прво проверавамо да је вредност кључа присутна а затим да читамо вредност тог кључа, могуће је користити метод TryGetValue који вредност чита само у једном обиласку речника (уместо у два). На пример,

string mesec = Console.ReadLine();
int broj;
if (brojDana.TryGetValue(mesec, out broj))
   Console.WriteLine("Broj dana: " + broj);
else
   Console.WriteLine("Mesec nije korektno unet");

Све елементе речника могуће је исписати коришћењем петље foreach. На пример,

foreach (var x in brojDana)
     Console.WriteLine(x.Key + ": " + x.Value);

Редослед обиласка није лако унапред предвидети. Ако желимо да будемо сигурни да ће се кључеви обилазити у сортираном редоследу, можемо уместо Dictionary употребити SortedDictionary. Ова варијанта може бити мало спорија него Dictionary, али то је обично занемариво. Кључеви сортиране мапе могу бити само они типови који се могу поредити (методом CompareTo), док кључеви неуређене мапе могу бити само они типови који се могу лако претворити у број (тзв. хеш-вредност) методом GetHashCode. Ниске, које ћемо најчешће користити као кључеве, задовољавају оба услова.